蛮三刀酱的博客

技术公众号:后端技术漫谈

【Leetcode】【python】Binary Tree Preorder Traversal 二叉树的前序遍历

发表于 更新于 分类于 阅读次数： Valine：

题目大意

二叉树前序遍历
挑战：迭代解题

解题思路

递归简单

迭代思路：见下方代码前

1
2
3
4
5
6
7
8
9
			　　1

　　　　　　　/     \

　　　　　 2         3

　　　 /     \    /    \

　　  4       5  6      7

代码

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def _preorderTraversal(self, root, result):
        if root:
            result.append(root.val)
            self._preorderTraversal(root.left, result)
            self._preorderTraversal(root.right, result)
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root == None:
            return []
        result = []
        self._preorderTraversal(root, result)
        return result

迭代

1.根节点入栈
2.取出节点，值加入结果，然后先加右，后加左。
3.重复2

注意：就算节点没有孩子，其指向孩子的指针（node.left）是None，不会报错

但是如果取值node.left.val，则会报错。所以最好是像要判断一下if node.left/right，因为这样栈中就不会有None，多浪费了时间。

1
2
3
4
5
6
7
8
9
10
while stack:
    node = stack.pop()
    if node:
        ret.append(node.val)
        stack.append(node.right)
        stack.append(node.left)

<precompiled.treenode.TreeNode object at 0x7f19ec21fc90>
None
None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ret = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                ret.append(node.val)
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
        return ret

总结